(1) Field of the Invention
This invention relates to a method and apparatus for generating a test sequence to test a fault in a digital circuit.
(2) Description of the Related Art
The adaption of LSI to a digital circuit has been remarkable these days, being utilized in every field. A technique of testing a fault in the LSI has been of great importance in accordance with the progress of the LSI since signals therein are not directly observable and controllable.
Various methods have been presented to automatically generate a test sequence for testing a fault in a digital circuit. Generally, the presence of a fault is checked by first inputting an appropriate input sequence to an input terminal of a circuit to be tested and then comparing the resulting output of an output terminal of the circuit with an expected output. This input sequence is the test sequence, which is generated to detect every presumed fault.
Conventional test sequence generation methods are disclosed, for example, in Chapter 1, 1.4.2 "Stuck at Fault Testing" of a reference book entitled "FAULT TOLERANT COMPUTING: THEORY AND TECHNIQUES", Volume I, issued by PRENTICE-HALL, Englewood Cliff, N.J. and "HITEC: A TEST GENERATION PACKAGE FOR SEQUENTIAL CIRCUITS" by T. Niermann and J. H. Patel, as a reference of European Design Automation Conference in 1991.
Such conventional test sequence generation method is detailed as follows:
A fault to be detected is a stuck-at fault, which is a model fault assumed based on a circuit to be tested. Such a fault causes a value of a signal lane in the circuit to be fixed to either a logical 0 or a logical 1, which are respectively referred to as "stuck-at-0 fault" and "stuck-at-1 fault". These stuck-at faults are previously registered on a fault table as shown in FIG. 1 based on the net list of the circuit. The table contains five columns: "signal lines" indicating all the signal lines in the circuit, "faults" indicating either stuck-at-0 fault (s-a-0) or stuck-at-1 fault (s-a-1), "detection" indicating successful detection or detectability by a test sequence for another fault by a 1, "process" indicating the completion of a test sequence generation process by a 1 (it does not matter whether the process is successful or not), and "redundant faults" indicating redundancy i.e. undetectability of a fault by a 1. For example, s-a-0 in the signal line "a" has been found not to be a redundant fault through the process and a test sequence has been successfully generated, on the other hand, s-a-1 in the signal line "c" has been found not to be a redundant fault and the generation of a test sequence has been unsuccessful.
This conventional test sequence generation method in a sequential circuit is flowcharted in FIG.
In the flowchart, the test sequence generation process starts at Step 401.
In Step 402, it is judged whether there is any fault except redundant faults for which a test sequence has not been generated yet (hereinafter referred to as undetected fault) and for which a test sequence generation process has not been performed yet (hereinafter referred to as unprocessed fault). If there is, then the system that executes this process proceeds to Step 403, and otherwise the system goes to Step 408 to terminate the process.
In Step 403, among undetected and unprocessed faults, one fault for which a test sequence is generated (hereinafter referred to as target fault) is selected, and at the same time, the corresponding row in the column "process" is made a 1.
In Step 404, a test pattern for a target fault is generated as a primary step for the test sequence generation, only for the combinational circuit to check whether the fault is a logically undetectable fault (hereinafter referred to as redundant fault). When the target fault is found to be a redundant fault or requires more time than allowed to generate a test sequence, the corresponding row in the column "redundant fault" is made a 1 and the system goes back to Step 402. In Step 404, such an undetectable fault is excluded before the test sequence generation.
In step 405, a test sequence for the target fault selected in Step 403 is generated to propagate the effects of the target fault from the fault site to any external output pin (hereinafter referred to as fault propagation process). If the fault propagation process is successful, then the system proceeds to Step 406, and otherwise the system goes back to Step 402 to process the next target fault.
In Step 406, a test sequence is generated to transfer the initial state of the circuit to a state appeared when the fault propagation process has been just completed (hereinafter referred to as state initialization process). If the process is successful, then the system proceeds to Step 407, and otherwise the system goes back to Step 402 to process the next target fault. The initial state may be any state; however, in general, as long as all the flip-flops (hereinafter referred to as FFs) in the circuit to be tested are either in "don't care" state or unknown state, a test sequence by which a fault test can be performed in whatever state the sequential circuit may be can be obtained. Actually, when the circuit is in a state appeared when an immediately preceding fault test has been just completed, the time required for consecutive fault tests can be shortened.
In Step 407, a fault simulation is performed with the test sequence of the target fault selected in Step 403 and the corresponding row in the column "detection" is made a 1. More than one target fault may be detected because all the faults in the common path are simulated simultaneously.
In Step 408, the test sequence generation process terminates.
The fault propagation process of Step 405, which is based on Reverse Time Processing (RTP), is flowcharted in .FIG. 3. According to RTP, a sequential circuit logically consisting of a combinational circuit and FFs is treated as a series of combinational circuits iterated in time sequence that are still logically equal to the sequential circuit. In the series of circuits, a path extending from an external output to be the goal of the target fault up to the fault site is heuristically determined and traced backward, and then an input sequence for the fault signal to be propagated along the path is found by the fault propagation process. In this process, an input for the fault signal of the target fault to propagate is found at each iterated combinational circuit (hereinafter referred to as time frame), that is, the path is activated.
More precisely, the following steps are executed in each time frame as shown in FIG. 3: In the flowchart, the fault propagation processing starts at Step 601.
In Step 602, it is judged whether a path including a target fault has been sensitized or not. If it has, then the fault propagation process is regarded as a success. The system goes to Step 605, and otherwise it proceeds to Step 603.
In Step 603, the target fault site or one of the outputs of the FFs corresponding to the inputs of the combinational circuit is selected as a D-frontier. Then, the D-frontier is assigned a fault signal and then the fault signal is propagated to either any external output pin or to the input of the D-frontier selected in an immediately preceding time frame (hereinafter referred to as target PPO) by assigning input values and state values respectively to the external input pins and the outputs of the FFs. If the fault propagation process is successful, then the system goes to Step 604, and otherwise it goes to Step 605.
In Step 604, the state values thus assigned to the external input pins to sensitize the fault propagation path are memorized as a test sequence, the system going to Step 602 with the input of an FF whose output is the D-frontier as a new target PPO.
In Step 605, the fault propagation process terminates.
The state initialization process of Step 406 is flowcharted in FIG. 4. In this process, an input sequence is generated based on state values assigned so that the state transition starts from a state appeared when the fault propagation process has been just completed (hereinafter referred to as fault excitement state), tracing backward to the initial state, contrary to the state transition in an actual fault test.
In FIG. 4, the state initialization process starts at Step 501.
In Step 502, it is judged whether the current state of the circuit coincides with its initial state or not. If they are coincident, then the system goes to Step 505 to terminate the process, and otherwise the system proceeds to Step 503.
In Step 503, the current state is justified by assigning state values to the outputs of the external input pins and of the FFs. If the justification is successful, then the system proceeds to Step 504, and otherwise it goes to Step 505 to terminate the process.
In Step 504, the state values thus assigned to the external input pins are memorized as a test sequence, whereas the state values assigned to the outputs of the FFs, that is, the state values that have justified the current state are defined as the current state. Then the system goes back to Step 502.
In Step 505, the state initialization process terminates.
The operation of the test sequence generation having the above-mentioned construction is described as follows:
First, a target fault is selected among undetected and unprocessed faults shown in the fault table in FIG. 1 (Steps 401-403 in FIG. 2).
Then, a test pattern for the combinational circuit in a circuit to be tested is generated to check whether the selected target fault is a redundant fault or requires extra time for the process. The circuit to be tested is illustrated in FIG. 5(a) and its simplified diagram is shown in FIG. 5 (b). Since the circuit can be logically divided into a combinational circuit and FFs, it is considered that the inputs of the combinational circuit consist of external input pins, which are primary inputs (hereinafter referred to as PIs) and pseudo primary inputs (hereinafter referred to as PPIs) outputted from the FFs, whereas the outputs of the combinational circuit consist of the external output pins, which are primary outputs (hereinafter referred to as POs) and pseudo primary outputs inputted to the FFs (hereinafter referred to as PPOs).
A test pattern for the combinational circuit is generated by assigning each appropriate input value by utilizing the PIs and PPIs of the inputs as well as the POs and PPOs of the outputs of the combinational circuit, so that the fault signal of a target fault is propagated to any output in Step 404. As a result, when the test pattern generation is successful, the system proceeds to Step 405, whereas if the target fault is a redundant fault, a 1 is set in the column of the "redundant fault" in the fault table, and the system goes back to Step 402 to select the next target fault.
In Step 405, a fault propagation process is executed to generate a test sequence for the target fault as shown in FIG. 6. The drawing contains three time frames 701, 702, and 703 in the sequential circuit, which are processed first, second, and third respectively. These time frames correspond to the combinational circuit expanded according to the state transition of the FFs separated from the combinational circuit. (For reference, the circuit of FIG. 5(b) is expanded and shown in FIG. 7).
Although only three time frames are shown in FIG. 6 for convenience, rather numerous time frames are required in an actual LSI. It should be noted that the fault propagation process proceeds reversely from the time frame 701 up to the time from 703 against the actual operation of a sequential circuit. FIG. 6 further contains an external output pin 704 of the sequential circuit, a propagation path 705 of a fault signal in the time frame 701, another fault propagation path 706 in the time frame 702, FFs 707-709 used in the time frame 701, FFs 710-712 used in the time frame 702, and a fault site 713 for the target fault "a".
The fault propagation process flowcharted in FIG. 3 is detailed as follows with reference to FIG. 6: In the first time frame 701, the target fault 713 can not be sensitized due to being unreachable to POs combinationally (Step 602 in FIG. 3), so that the output of FF3 (709) is heuristically selected as a D-frontier. The fault propagation path 705 is sensitized to assign a fault signal to FF3 (709) and propagate it to the external output pin 704. In other words, state values are assigned to the external input pins and the FFs to sensitize the path leading from FF3 (709) up to the external output pin 704 (Step 603). The state values successfully assigned are memorized as a test sequence, and the input of FF3 whose input is the D-frontier, is set as a new target PPO. Then the system goes back to Step 602 (Step 604). Since the target fault has not been sensitized yet at this point, the system proceeds to Step 603 (Step 602).
In the next time frame 702, the output of FF3 (709) selected as a D-frontier in the time frame 701 is made a target PPO, and FF2 (711) is heuristically selected as a D-frontier. Then FF2 (711) is assigned a fault signal and the fault signal is propagated to the input of FF3 (709) as a target PPO by sensitizing the fault propagation path 706 (Step 603). The successfully assigned state value is memorized as a test sequence, and the input of FF2 is set as a new target PPO (Step 604).
In the next time frame 703, the output of FF2 (711) is selected in the time frame 702 as a D-frontier is made a target PPO. It is assumed that a fault signal can not be propagated to the input of FF2 (711) as the target PPO whichever D-frontier is selected (Step 603). Since the fault propagation process for the fault 713 is thus unsuccessful, the fault propagation process terminates (Step 604). Subsequently, the system goes back to Step 402 in FIG. 2 (Step 405) to select the next target fault and to repeat the same process (Steps 402-405).
On the other hand, when the fault signal is successfully propagated to the target fault 713 in the time frame 703, the state values assigned to the external input pins in each time frame are generated as a test sequence. However, the state of each FF is in the fault excitement state (In the above case, it corresponds to the state value successfully assigned in the time frame 703), so that the test sequence thus generated is only effective to the fault excitement state. Therefore, finding a sequence to transfer the initial state of the circuit to its fault excitement state is required. This is the state initialization process.
The operation of the state initialization process is described as follows with reference FIG. 8.
In the drawing, numerals 801-804 depict each state of the circuit, 801 representing a fault excitement state, 804 representing an initial state. Branches 805-808 depict the possibility of transitions respectively from state 802 to state 801, from state 803 to state 802, from state 801 to state 803, and from state 804 to state 803.
At the point of the completion of the fault propagation process, the current state is the state 801 (S1), which does not coincide with the initial state (Step 502 in FIG. 4). Therefore, the current state is justified, that is, the states of the external inputs and of the FFs are assigned so that the current state can be transferred. Here, it is assumed that the assignment of the state 802 (S2) to the FFs is justified (Step 503). The justified state is treated as a new current state (S2) (Step 504).
The current state is justified in the same manner and the state S3 is made a new current state (Steps 502-504).
In the justification of the current state S3, the current state S3 may be transferred from either one of the states S1 and S4. When the justified state is the state S4, the state initialization is successful. In this case, a fault test sequence can be obtained by combining an input sequence obtained in the previous fault propagation process and another input sequence assigned in the state initialization process.
On the contrary, when the justified state is the state S1, the state initialization is unsuccessfully repeated, going into a loop of a state transition, never obtaining the initial state.
After the state initialization process is performed, a fault simulation is executed for the target fault with the use of the obtained test sequence. After having confirmed that the target fault is detectable by the external output pins, the corresponding row in the column "detection" is made a 1 (Step 407 in FIG. 2). Then the system goes back to Step 402. The foregoing behavior is further repeated to execute the test sequence generation process for every target fault.
Finally, the test sequence generation process in the circuit in FIG. 7 is described as follows. The "X" marks on the signal lines represent target faults.